A SVD accelerated kernel-independent fast multipole method and its application to BEM

摘要

The kernel-independent fast multipole method (KIFMM) proposed in [1] is ofalmost linear complexity. In the original KIFMM the time-consuming M2Ltranslations are accelerated by FFT. However, when more equivalent points areused to achieve higher accuracy, the efficiency of the FFT approach tends to belower because more auxiliary volume grid points have to be added. In thispaper, all the translations of the KIFMM are accelerated by using the singularvalue decomposition (SVD) based on the low-rank property of the translatingmatrices. The acceleration of M2L is realized by first transforming theassociated translating matrices into more compact form, and then using low-rankapproximations. By using the transform matrices for M2L, the orders of thetranslating matrices in upward and downward passes are also reduced. Theimproved KIFMM is then applied to accelerate BEM. The performance of theproposed algorithms are demonstrated by three examples. Numerical results showthat, compared with the original KIFMM, the present method can reduce about 40%of the iterating time and 25% of the memory requirement.